import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description: 优选算法day5：二分查找
 * User: 姚东名
 * Date: 2024-12-17
 * Time: 19:54
 */
public class Test {
    // 17. ⼆分查找（easy）
    public static int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    public static void main1(String[] args) {
        int[] nums = {-1, 0, 3, 5, 9, 12};
        int target = 9;
        int result = search(nums, target);
        System.out.println(result);
    }

    // 18. 在排序数组中查找元素的第⼀个和最后⼀个位置（medium）
    /**
     * 1. 查找左端点思路:
     *
     * 1）初始化指针：
     * 首先定义两个指针，left 指针初始指向数组的第一个元素位置（下标为 0），right 指针初始指向数组的最后一个元素位置（下标为 nums.length - 1）。
     * 这两个指针界定了我们进行查找的范围区间。
     *
     * 2）循环查找：
     * 进入一个 while 循环，循环条件通常设置为 left < right。之所以是严格小于，是因为我们要不断缩小区间，
     * 直到 left 和 right 重合，此时 left 所指向的位置就是我们要找的目标值的左端点位置。
     *
     * 3）计算中间位置并判断：
     * 在循环内，先计算中间元素的下标 mid，一般采用 mid = left + (right - left) / 2 的方式
     * （这样能避免整数溢出问题，相较于 (left + right) / 2 更安全）。
     * 然后比较中间元素 nums[mid] 和目标值 target 的大小关系：
     * 当 nums[mid] < target 时：意味着目标值在中间元素的右侧区间，此时需要更新 left 指针，将 left 赋值为 mid + 1，
     * 这样就把查找范围缩小到了中间元素右侧的区间，下次循环就在新的区间内继续查找。
     * 当 nums[mid] >= target 时：说明目标值可能就在中间元素这个位置或者在其左侧区间，所以将 right 指针更新为 mid，
     * 让查找范围缩小到中间元素及其左侧区间，后续循环就在这个新缩小的区间里继续查找。
     *
     * 4）例如，对于数组 [1, 2, 2, 3, 3, 3]，目标值为 3。一开始 left = 0，right = 5，第一次计算 mid = 2，nums[mid] = 2 小于目标值 3，
     * 则更新 left = mid + 1 = 3；第二次计算 mid = 4，nums[mid] = 3 等于目标值，
     * 此时更新 right = mid = 4；再次循环，mid = 3，nums[mid] = 3，依然更新 right = mid = 3，
     * 此时 left 和 right 重合，left = 3 就是目标值 3 的左端点位置。
     *
     * 2. 查找右端点思路:
     *
     * 1）同样的初始化指针：
     * 也是设置 left 指针初始为数组第一个元素位置（下标 0），right 指针初始为数组最后一个元素位置（下标 nums.length - 1），
     * 来界定查找的范围区间。
     *
     * 2）类似的循环查找：
     * 同样通过 while 循环进行查找，循环条件同样常为 left < right，目的也是不断缩小区间直至找到目标值的右端点位置，
     * 最终 left 所指就是我们要的右端点。
     *
     * 3）关键的中间位置计算与判断差异：
     * 计算中间元素下标 mid 时，这里一般采用 mid = left + (right - left + 1) / 2 的方式
     * （这是为了确保在一些边界情况，比如 left 和 right 相邻时，能正确地逼近目标值的右端点）。
     * 然后再比较中间元素 nums[mid] 和目标值 target 的大小关系：
     * 当 nums[mid] > target 时：表明目标值在中间元素的左侧区间，需要更新 right 指针，将 right 赋值为 mid - 1，
     * 把查找范围缩小到中间元素左侧区间，后续就在新的区间内继续查找。
     * 当 nums[mid] <= target 时：意味着目标值可能就在中间元素这个位置或者在其右侧区间，所以把 left 指针更新为 mid，
     * 使查找范围缩小到中间元素及其右侧区间，接着在新的区间继续查找。
     *
     * 4）例如，还是对于数组 [1, 2, 2, 3, 3, 3]，目标值为 3。开始 left = 0，right = 5，
     * 第一次计算 mid = 3（按照 mid = left + (right - left + 1) / 2 计算），
     * nums[mid] = 3 等于目标值，更新 left = mid = 3；第二次计算 mid = 4，nums[mid] = 3
     * 也等于目标值，继续更新 left = mid = 4；此时 left 和 right 重合，left = 4 就是目标值 3 的右端点位置。
     *
     * 总的来说，查找左端点和右端点都是基于二分查找的思想，通过不断缩小区间来逼近目标值对应的边界位置，
     * 但在中间位置计算以及根据比较结果更新指针的细节上有所不同，以准确找到各自的端点。
     */
    public static int[] searchRange(int[] nums, int target) {
        int[] ret = new int[2];
        ret[0] = ret[1] = -1;
        // 处理特殊情况
        if (nums.length == 0) {
            return ret;
        }
        int left = 0;
        int right = nums.length - 1;
        // 二分查找左端点
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                // nums[mid] >= target
                right = mid;
            }
        }
        // 判断是否有结果
        if (nums[left] != target) {
            return ret;
        } else {
            ret[0] = left;
        }

        // 二分查找右端点
        left = 0;
        right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        ret[1] = left;
        return ret;
    }

    // 换种写法：
    public static int[] searchRange1(int[] nums, int target) {
        int[] result = {-1, -1};
        // 查找左边界
        int left = binarySearchLeft(nums, target);
        if (left == nums.length || nums[left]!= target) {
            return result;
        }
        // 查找右边界
        int right = binarySearchRight(nums, target);
        result[0] = left;
        result[1] = right;
        return result;
    }

    private static int binarySearchLeft(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private static int binarySearchRight(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 8, 10};
        int target = 8;
        int[] range = searchRange1(nums, target);
        System.out.println(Arrays.toString(range));
    }
}
